package chapter1.section2;

import org.junit.Test;

/**
 * 给定一长字符串a和一断字符串b，请问，如何最快的判断出短字符串b中的所有字符是否都在长字符串a中？
 * 请编写方法boolean stringContain(String a,String b)实现此功能。为简单起见，假设输入的字符只包含大写英文字母。
 * @author lidd
 *
 */
/*
 * 解法四：位运算法,时间复杂度O(m+n),空间复杂度为O(1)
 * 这种方法有点难理解，确实挺好的，只要b中的字符在a中全有，那么第二个for语句的判断值肯定为1，只要有一个没有肯定为0
 * 可以debug来理解
 */
public class StringContain4 {

	public boolean stringContain(String a, String b) {
		int hash = 0;
		for(int i = 0; i < a.length(); i++) {
			hash |= (1 << (a.charAt(i) - 'A'));
		}
		for(int i = 0; i < b.length(); i++) {
			if((hash & (1 << (b.charAt(i) - 'A'))) == 0) {
				return false;
			}
		}
		return true;
	}
	
	//测试方法
		@Test
		public void test() {
			String a = "ABCE";
			String b = "AF";
			boolean bool = stringContain(a, b);
			System.out.println(bool);
		}
		
}
